using System;
using System.Collections.Generic;
using System.Drawing;
using System.Reflection;
using System.Text;

namespace Solution
{
    internal class Program
    {


        static int move = 0;

        static void Main(string[] args)
        {
            while (true)
            {
                Console.WriteLine("\n准备开始:");
                Console.WriteLine("1. 继续测试");
                Console.WriteLine("其他: 结束程序");
                string choice = Console.ReadLine();
                if (!choice.Equals("1"))
                {
                    break;
                }
                Console.WriteLine("继续测试, 请输入: ");
                Console.WriteLine("输入一个字符串: ");
                string s = Console.ReadLine();
                StringBuilder sb = new StringBuilder();
                sb.Append(s);
                Console.WriteLine(sb.ToString());
                Console.WriteLine("反转字符串......");
                Console.WriteLine(s.ToCharArray());
                Console.WriteLine(s.ToCharArray());
                Console.WriteLine(ReverseString(s.ToCharArray()));

                //System.Console.WriteLine("调用核心代码: leetcode 210 课程表Ⅱ FindOrder");
            }
        }

        /// <summary>
        /// leetcode  1047  删除字符串中的所有相邻重复项
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public string RemoveDuplicates(string s)
        {
            Stack<char> stack = new Stack<char>();
            for (int i = s.Length - 1; i >= 0; i--)
            {

                if (stack.Count > 0 && s[i] == stack.Peek())
                {
                    stack.Pop();
                }
                else
                    stack.Push(s[i]);
            }
            StringBuilder sb = new StringBuilder();
            while (stack.Count > 0)
            {
                sb.Append(stack.Pop());
            }

            return sb.ToString();
        }

        /// <summary>
        /// leetcode  2596  检查骑士巡视方案
        /// </summary>
        /// <param name="grid"></param>
        /// <returns></returns>
        public bool CheckValidGrid(int[][] grid)
        {
            if (grid[0][0] != 0)
                return false;

            int n = grid.Length;
            int[][] path = new int[n * n][];

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    path[grid[i][j]] = new int[] { i, j };
                }
            }
            for (int i = 1; i < n * n; i++)
            {
                int row = Math.Abs(path[i - 1][0] - path[i][0]);
                int col = Math.Abs(path[i - 1][1] - path[i][1]);
                if (row * col != 2)
                {
                    return false;
                }
            }

            return true;
        }

        /// <summary>
        /// leetcode  239  滑动窗口的最大值
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int[] MaxSlidingWindow(int[] nums, int k)
        {
            if (nums == null || nums.Length < 2) return nums;
            // 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序
            LinkedList<int> queue = new LinkedList<int>();
            // 结果数组
            int[] result = new int[nums.Length - k + 1];
            // 遍历nums数组
            for (int i = 0; i < nums.Length; i++)
            {
                // 保证从大到小 如果前面数小则需要依次弹出，直至满足要求
                while (queue.Count > 0 && nums[queue.Last.Value] <= nums[i])
                {
                    queue.RemoveLast();
                }
                // 添加当前值对应的数组下标
                queue.AddLast(i);
                // 判断当前队列中队首的值是否有效
                if (queue.First.Value <= i - k)
                {
                    queue.RemoveFirst();
                }
                // 当窗口长度为k时 保存当前窗口中最大值
                if (i + 1 >= k)
                {
                    result[i + 1 - k] = nums[queue.First.Value];
                }
            }

            return result;
        }

        /// <summary>
        /// leetcode  1462  课程表4
        /// </summary>
        /// <param name="numCourses"></param>
        /// <param name="prerequisites"></param>
        /// <param name="queries"></param>
        /// <returns></returns>
        public IList<bool> CheckIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries)
        {
            List<List<int>> list = new List<List<int>>();
            int[] require = new int[numCourses];
            Queue<int> queue = new Queue<int>();
            bool[][] isPre = new bool[numCourses][];
            List<bool> res = new List<bool>();

            for (int i = 0; i < numCourses; i++)
            {
                list.Add(new List<int>());
                isPre[i] = new bool[numCourses];
            }
            foreach (var item in prerequisites)
            {
                require[item[1]]++;
                list[item[0]].Add(item[1]);
            }

            for (int i = 0; i < numCourses; i++)
            {
                if (require[i] == 0)
                    queue.Enqueue(i);
            }

            while (queue.Count > 0)
            {
                int cur = queue.Dequeue();
                foreach (var next in list[cur])
                {
                    isPre[cur][next] = true;
                    for (int i = 0; i < numCourses; i++)
                    {
                        isPre[i][next] = isPre[i][next] || isPre[i][cur];
                    }
                    if (--require[next] == 0)
                    {
                        queue.Enqueue(next);
                    }
                }
            }

            foreach (var item in queries)
            {
                res.Add(isPre[item[0]][item[1]]);
            }
            return res;
        }

        /// <summary>
        /// leetcode  541  反转字符串2
        /// </summary>
        /// <param name="s"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public string ReverseStr(string s, int k)
        {
            int n = s.Length;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i += 2 * k)
            {
                if (i + k > n)
                {
                    string temp = s.Substring(i, n - 1 - i);
                    sb.Append(ReverseString(temp.ToCharArray()));
                }
                else if (i + 2 * k > n)
                {
                    string temp = s.Substring(i, k);
                    sb.Append(ReverseString(temp.ToCharArray()));
                    sb.Append(s.Substring(i + k, n - i - k));
                }
                else
                {
                    string temp = s.Substring(i, k);
                    sb.Append(ReverseString(temp.ToCharArray()));
                    sb.Append(s.Substring(i + k, k));
                }
            }
            return sb.ToString();
        }

        /// <summary>
        /// leetcode  459  重复的子字符串
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static bool RepeatedSubstringPattern(string s)
        {
            int n = s.Length;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n / 2; i++)
            {
                string temp = s.Substring(0, i + 1);
                sb.Append(temp);
                if (n % (i + 1) == 0)
                {
                    for (int j = 1; j < n / (i + 1); j++)
                    {
                        sb.Append(temp);
                    }
                    if (sb.Equals(s))
                        return true;
                }
                sb.Clear();
            }
            return false;
        }

        /// <summary>
        /// leetcode  210  课程表Ⅱ
        /// </summary>
        /// <param name="numCourses"></param>
        /// <param name="prerequisites"></param>
        /// <returns></returns>
        public static int[] FindOrder(int numCourses, int[][] prerequisites)
        {
            List<List<int>> list = new List<List<int>>();
            int[] require = new int[numCourses];
            int[] res = new int[numCourses];
            int left = 0, right = 0;

            for (int i = 0; i < numCourses; i++)
            {
                list.Add(new List<int>());
            }

            foreach (var item in prerequisites)
            {
                require[item[0]]++;
                list[item[1]].Add(item[0]);
            }

            for (int i = 0; i < numCourses; i++)
            {
                if (require[i] == 0)
                    res[right++] = i;
            }

            while (left < right)
            {
                int currentCourse = res[left++];
                foreach (var next in list[currentCourse])
                {
                    if (--require[next] == 0)
                        res[right++] = next;
                }
            }
            if (left != numCourses)
                return res;
            else
                return new int[] { };
        }

        /// <summary>
        /// leetcode 剑指 Offer 05 替换空格
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public string ReplaceSpace(string s)
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] != ' ')
                {
                    sb.Append(s[i]);
                }
                else
                {
                    sb.Append("%20");
                }
            }
            return sb.ToString();
        }

        /// <summary>
        /// leetcode  151  反转字符串中的单词
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static string ReverseWords(string s)
        {
            Stack<string> stack = new Stack<string>();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] != ' ')
                {
                    sb.Append(s[i]);
                }
                else if (sb.Length != 0)
                {
                    stack.Push(sb.ToString());
                    sb.Clear();
                }
            }
            if (sb != null)
            {
                stack.Push(sb.ToString());
                sb.Clear();
            }

            string[] strings = stack.ToArray();

            return string.Join(' ', strings);
        }

        /// <summary>
        /// leetcode  28  找出字符串中第一个匹配的下标
        /// </summary>
        /// <param name="haystack"></param>
        /// <param name="needle"></param>
        /// <returns></returns>
        public static int StrStr(string haystack, string needle)
        {
            if (needle.Length == 0)
                return -1;
            int m = haystack.Length;
            int n = needle.Length;
            bool flag = false;
            int next = 0;
            char first = needle[0];
            for (int i = 0; i <= m - n; i++)
            {
                if (haystack[i] == needle[0])
                {
                    int j = 0;
                    while (j < n && haystack[i + j] == needle[j])
                    {
                        if (haystack[i + j] == first && j != 0 && !flag)
                        {
                            next = i + j;
                            flag = true;
                        }
                        j++;
                    }
                    if (j == n)
                        return i;
                    if (flag)
                    {
                        flag = false;
                        i = next - 1;
                    }
                }
            }

            return -1;
        }

        /// <summary>
        /// leetcode  207  课程表
        /// </summary>
        /// <param name="numCourses"></param>
        /// <param name="prerequisites"></param>
        /// <returns></returns>
        public bool CanFinish(int numCourses, int[][] prerequisites)
        {
            // 前置课程对应的的后续课程
            List<List<int>> list = new List<List<int>>();
            // 选修课程顺序
            Queue<int> queue = new Queue<int>();
            // 前置课程数量
            int[] require = new int[numCourses];

            for (int i = 0; i < numCourses; i++)
            {
                list.Add(new List<int>());
            }

            foreach (var item in prerequisites)
            {
                // 前置课程数量 +1
                require[item[0]]++;
                // 前置课程列表添加
                list[item[1]].Add(item[0]);
            }

            for (int i = 0; i < numCourses; i++)
            {
                // 没有前置课程，入队
                if (require[i] == 0)
                    queue.Enqueue(i);
            }

            while (queue.Count > 0)
            {
                int pre = queue.Dequeue();
                numCourses--;
                foreach (var next in list[pre])
                {
                    if (--require[next] == 0)
                        queue.Enqueue(next);
                }
            }

            return numCourses == 0;

        }

        /// <summary>
        /// leetcode  49  快乐数
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public bool IsHappy(int n)
        {
            HashSet<int> hash = new HashSet<int>();
            while (n != 1 && !hash.Contains(n))
            {
                hash.Add(n);
                n = GetNextNum(n);
            }
            return n == 1;
        }

        int GetNextNum(int n)
        {
            int sum = 0;
            while (n > 0)
            {
                int temp = n % 10;
                sum += temp * temp;
                n /= 10;
            }
            return sum;
        }

        /// <summary>
        /// leecode 2651  计算列车到站时间
        /// </summary>
        /// <param name="arrivalTime"></param>
        /// <param name="delayedTime"></param>
        /// <returns></returns>
        public int FindDelayedArrivalTime(int arrivalTime, int delayedTime)
        {
            return (arrivalTime + delayedTime) % 24;
        }

        /// <summary>
        /// 4
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="nums2"></param>
        /// <returns></returns>
        public double FindMedianSortedArrays(int[] nums1, int[] nums2)
        {
            int n1 = nums1.Length, n2 = nums2.Length;
            int n = n1 + n2;
            if (n1 == 0 || n2 == 0)
            {
                if (n % 2 == 0)
                {
                    if (n1 == 0)
                        return (nums2[n / 2 - 1] + nums2[n / 2]) / 2;
                    else
                        return (nums1[n / 2 - 1] + nums1[n / 2]) / 2;
                }
                else
                {
                    if (n1 == 0)
                        return nums2[n / 2];
                    else
                        return nums1[n / 2];
                }
            }
            int pre = Math.Min(nums1[0], nums2[0]);
            int index1 = -1, index2 = -1, index = -1;
            while (index < n / 2)
            {

            }


            if (n % 2 == 0)
            {
                // int index1 = n / 2 - 1;
                // int index2 = n / 2;


            }

            return 0;
        }

        /// <summary>
        /// leetcode  2594  修车的最少时间
        /// </summary>
        /// <param name="ranks"></param>
        /// <param name="cars"></param>
        /// <returns></returns>
        public long RepairCars(int[] ranks, int cars)
        {
            long left = 1, right = (long)ranks[0] * cars * cars;
            while (left < right)
            {
                long mid = (left + right) / 2;
                if (Check(ranks, cars, mid))
                    right = mid;
                else
                    left = mid + 1;
            }
            return left;
        }

        bool Check(int[] ranks, int cars, long mid)
        {
            long count = 0;
            foreach (var item in ranks)
            {
                count += (long)Math.Sqrt(mid / item);
            }
            return count >= cars;
        }

        

        /// <summary>
        /// leetcode  3  无重复字符的子串
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int LengthOfLongestSubstring(string s)
        {
            if (s.Length == 0)
                return 0;
            Dictionary<char, int> dict = new Dictionary<char, int>();
            int left = 0;
            int res = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (dict.ContainsKey(s[i]))
                {
                    // res = i - index > res ? i - index : res;
                    // index = i;
                    left = Math.Max(left, dict[s[i]]);
                    dict.Remove(s[i]);
                }
                res = Math.Max(res, i - left + 1);
                dict.Add(s[i], i);
            }

            return res;
        }

        /// <summary>
        /// leetcode 2605 从两个数字数组里生成最小数字
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="nums2"></param>
        /// <returns></returns>
        public int MinNumber(int[] nums1, int[] nums2)
        {
            int[] count = new int[9];
            int min1 = 9, min2 = 9;
            for (int i = 0; i < nums1.Length; i++)
            {
                count[nums1[i] - 1]++;
                if (nums1[i] < min1)
                    min1 = nums1[i];
            }
            for (int i = 0; i < nums2.Length; i++)
            {
                count[nums2[i] - 1]++;
                if (nums2[i] < min2)
                    min2 = nums2[i];
            }

            for (int i = 0; i < count.Length; i++)
            {
                if (count[i] == 2)
                    return i + 1;
            }

            if (min1 > min2)
            {
                int temp = min1;
                min1 = min2;
                min2 = temp;
            }

            return min1 * 10 + min2;
        }


        /// <summary>
        /// leetcode 449 serialize  297
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        // Encodes a tree to a single string.
        public string serialize(TreeNode root)
        {
            List<string> list = new List<string>();
            PostOrder(root, list);
            return string.Join(",", list);
        }

        /// <summary>
        /// leetcode 449 deserialize  297
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        // Decodes your encoded data to tree.
        public TreeNode deserialize(string data)
        {
            if (data.Length == 0)
                return null;
            string[] str = data.Split(",");
            Stack<string> stack = new Stack<string>();
            for (int i = 0; i < str.Length; i++)
            {
                stack.Push(str[i]);
            }

            return Construct(stack);
        }

        void PostOrder(TreeNode root, List<string> list)
        {
            if (root == null)
            {
                list.Add("none");
            }
            else
            {
                PostOrder(root.left, list);
                PostOrder(root.right, list);
                list.Add(root.val.ToString());
            }
        }

        TreeNode Construct(Stack<string> stack)
        {
            if (stack.Count == 0)
            {
                return null;
            }
            string str = stack.Pop();
            if (str.Equals("none"))
            {
                return null;
            }
            TreeNode root = new TreeNode(int.Parse(str));
            root.right = Construct(stack);
            root.left = Construct(stack);
            return root;
        }

        /// <summary>
        /// leetcode 2449
        /// </summary>
        /// <param name="dist"></param>
        /// <param name="speed"></param>
        /// <returns></returns>
        public int EliminateMaximum(int[] dist, int[] speed)
        {
            int res = 0;
            int n = dist.Length;
            float[] time = new float[n];
            for (int i = 0; i < n; i++)
            {
                time[i] = (float)dist[i] / speed[i];
            }

            Array.Sort(time);
            for (int i = 0; i < n; i++)
            {
                if (time[i] - res > 0)
                    res++;
                else
                    break;
            }
            return res;
        }


        public int RemoveDuplicates(int[] nums)
        {
            if (nums.Length == 0)
                return 0;
            int index = 1;
            for (int i = 1; i < nums.Length; i++)
            {
                if (nums[i] != nums[i - 1])
                {
                    nums[index] = nums[i];
                    index++;
                }
            }
            return index;
        }

        public int NumFactoredBinaryTrees(int[] arr)
        {
            Array.Sort(arr);
            int length = arr.Length;
            long res = 0, mod = 1000000007;
            long[] dp = new long[length];

            for (int i = 0; i < length; i++)
            {
                dp[i] = 1;
                for (int left = 0, right = i - 1; left <= right; left++)
                {
                    if (left <= right && (long)(arr[left] * arr[right]) > arr[i])
                    {
                        right--;
                    }
                    if (left <= right && (long)(arr[left] * arr[right]) == arr[i])
                    {
                        if (left != right)
                            dp[i] = (dp[i] + dp[left] * dp[right] * 2) % mod;
                        else
                            dp[i] = (dp[i] + dp[left] * dp[right]) % mod;
                    }
                }
                res = (res + dp[i]) % mod;
            }

            return (int)res;
        }
        public int[][] Insert(int[][] intervals, int[] newInterval)
        {
            List<int[]> list = new List<int[]>();

            int start = newInterval[0];
            int end = newInterval[1];
            int length = intervals.Length;
            bool isDone = false;

            for (int i = 0; i < length; i++)
            {
                if (end < intervals[i][0])
                {
                    if (!isDone)
                    {
                        list.Add(new int[] { start, end });
                        isDone = true;
                    }
                    list.Add(intervals[i]);
                }
                else if (start > intervals[i][1])
                {
                    list.Add(intervals[i]);
                }
                else
                {
                    start = Math.Min(start, intervals[i][0]);
                    end = Math.Max(end, intervals[i][1]);
                }
            }
            if (!isDone)
            {
                list.Add(new int[] { start, end });
                isDone = true;
            }

            return list.ToArray();
        }

        public int[][] Merge(int[][] intervals)
        {
            Array.Sort(intervals, (a, b) =>
            {
                if (a[0] != b[0])
                    return a[0] - b[0];
                else
                    return a[1] - b[1];
            });
            IList<int[]> mergedList = new List<int[]>();

            if (intervals.Length == 0)
                return new int[0][];

            mergedList.Add(intervals[0]);
            int length = intervals.Length;
            int start = intervals[0][0];
            int end = intervals[0][1];

            for (int i = 1; i < length; i++)
            {
                start = intervals[i][0];
                end = intervals[i][1];
                if (start > mergedList[mergedList.Count - 1][1])
                {
                    mergedList.Add(new int[] { start, end });
                }
                else
                {
                    mergedList[mergedList.Count - 1][1] = Math.Max(mergedList[mergedList.Count - 1][1], end);
                }
            }
            return mergedList.ToArray();

        }

        public bool CanJump(int[] nums)
        {
            int n = nums.Length;
            int i = 0;
            while (i < n)
            {
                if (nums[i] == 0)
                {

                }
            }


            return false;
        }


        public int GoodNodes(TreeNode root)
        {
            return GoodNodeDFS(root, int.MinValue);
        }

        public int GoodNodeDFS(TreeNode root, int max)
        {
            if (root == null)
            {
                return 0;
            }

            int res = 0;

            if (root.val >= max)
            {
                res++;
                max = root.val;
            }

            res += GoodNodeDFS(root.left, max) + GoodNodeDFS(root.right, max);

            return res;
        }

        public static int CountServers(int[,] grid, int m, int n)
        {
            //int m = grid.Length;
            //int n = grid[0].Length;

            int countAlone = 0;
            int countTotal = 0;
            int countTemp = 0;
            int[] row = new int[m];
            int[] col = new int[n];
            int index = -1;

            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (grid[i, j] == 1)
                    {
                        // grid[i][j] = 2;
                        countTotal++;
                        countTemp++;
                        // index = j;
                        row[i]++;
                        col[j]++;
                    }
                }

                if (countTemp == 1)
                {
                    countAlone++;
                    //col[index]++;
                }
                countTemp = 0;
                index = -1;
            }


            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (grid[i, j] == 1 && row[i] == 1 && col[j] == 1)
                    {
                        countTotal--;
                    }
                }


            }

            return countTotal;
        }

        static int SumOfPower(int[] nums)
        {
            IList<IList<int>> res = new List<IList<int>>();
            Backtrack(0, nums, res, new List<int>());

            long sum = 0;

            foreach (var item in res)
            {
                sum += GetMax(item) * GetMax(item) * GetMin(item);
                //max(nums[i0], nums[i1]... nums[ik])2 * min(nums[i0], nums[i1]... nums[ik])
            }
            return (int)(sum % 1000000007);
        }

        public static IList<IList<int>> Subsets(int[] nums)
        {
            IList<IList<int>> res = new List<IList<int>>();
            Backtrack(0, nums, res, new List<int>());
            return res;
        }

        static void Backtrack(int index, int[] nums, IList<IList<int>> res, IList<int> temp)
        {
            if (temp != null)
            {
                res.Add(new List<int>(temp));
            }
            for (int i = index; i < nums.Length; i++)
            {
                temp.Add(nums[i]);
                Backtrack(i + 1, nums, res, temp);
                temp.RemoveAt(temp.Count - 1);
            }

        }

        static int GetMax(IList<int> list)
        {
            int max = list[0];
            foreach (var item in list)
            {
                if (item > max) max = item;
            }
            return max;
        }

        static int GetMin(IList<int> list)
        {
            int min = list[0]; ;
            foreach (var item in list)
            {
                if (item < min) min = item;
            }
            return min;
        }

        public static long[] HandleQuery(int[] nums1, int[] nums2, int[][] queries)
        {
            List<long> list = new List<long>();
            for (int i = 0; i < queries.Length; i++)
            {
                switch (queries[i][0])
                {
                    case 1:
                        for (int j = queries[i][1]; j <= queries[i][2]; j++)
                        {
                            if (nums1[j] == 1)
                                nums1[j] = 0;
                            else if (nums1[j] == 0)
                                nums1[j] = 1;
                        }
                        break;
                    case 2:
                        int p = queries[i][1];
                        for (int j = 0; j < nums2.Length; j++)
                        {
                            nums2[j] = nums2[j] + nums1[j] * p;
                        }
                        break;
                    case 3:
                        long sum = 0;
                        for (int j = 0; j < nums2.Length; j++)
                        {
                            sum += nums2[j];
                        }
                        list.Add(sum);

                        break;
                }
            }

            return list.ToArray();
        }


        IList<IList<string>> res = new List<IList<string>>();
        bool[] usedCol, usedDiag45, usedDiag135;    // bool数组中的每个元素代表一条直(斜)线
        public IList<IList<string>> SolveNQueens(int n)
        {
            usedCol = new bool[n];                  // 列方向的直线条数为 n
            usedDiag45 = new bool[2 * n - 1];       // 45°方向的斜线条数为 2 * n - 1
            usedDiag135 = new bool[2 * n - 1];      // 135°方向的斜线条数为 2 * n - 1
                                                    //用于收集结果, 元素的index表示棋盘的row，元素的value代表棋盘的column
            int[] board = new int[n];
            BackTracking(board, n, 0);
            return res;
        }
        private void BackTracking(int[] board, int n, int row)
        {
            if (row == n)
            {
                //收集结果
                List<string> temp = new List<string>();
                foreach (var i in board)
                {
                    char[] str = new char[n];
                    Array.Fill(str, '.');
                    str[i] = 'Q';
                    temp.Add(new string(str));
                }
                res.Add(temp);
                return;
            }

            for (int col = 0; col < n; col++)
            {
                if (usedCol[col] | usedDiag45[row + col] | usedDiag135[row - col + n - 1])
                {
                    continue;
                }
                board[row] = col;
                // 标记该列出现过
                usedCol[col] = true;
                // 同一45°斜线上元素的row + col为定值, 且各不相同
                usedDiag45[row + col] = true;
                // 同一135°斜线上元素row - col为定值, 且各不相同
                // row - col 值有正有负, 加 n - 1 是为了对齐零点
                usedDiag135[row - col + n - 1] = true;
                // 递归
                BackTracking(board, n, row + 1);
                usedCol[col] = false;
                usedDiag45[row + col] = false;
                usedDiag135[row - col + n - 1] = false;
            }
        }


        public static int DistributeCoins(TreeNode root)
        {
            DFS(root);
            return move;
        }

        public static int DFS(TreeNode root)
        {
            int left = 0, right = 0;
            if (root == null)
            {
                return 0;
            }
            if (root.left != null)
            {
                left = DFS(root.left);
            }
            if (root.right != null)
            {
                right = DFS(root.right);
            }
            move = Math.Abs(left) + Math.Abs(right);
            return left + right + root.val - 1;
        }


        public static string ReverseString(char[] s)
        {
            char temp;
            int n = s.Length;
            for (int i = 0; i < s.Length / 2; i++)
            {
                temp = s[i];
                s[i] = s[n - i - 1];
                s[n - i - 1] = temp;
            }
            return new string(s);
        }


        public int AlternateDigitSum(int n)
        {
            int result = 0, sigh = 1;

            while (n > 0)
            {
                result += n % 10 * sigh;
                n /= 10;
                sigh = -sigh;
            }
            return result;
        }



        public static IList<int> FindDuplicates(int[] nums)
        {
            IList<int> res = new List<int>();
            for (int i = 0; i < nums.Length; i++)
            {
                int x = Math.Abs(nums[i]);
                if (nums[x - 1] > 0)
                    nums[x - 1] = -nums[x - 1];
                else
                    res.Add(x);
            }
            return res;
        }

        public static int MaxProfit(int k, int[] prices)
        {
            int n = prices.Length;
            int[] buy = new int[k + 1];
            int[] sell = new int[k + 1];
            for (int i = 1; i <= k; i++)
            {
                buy[i] = -prices[0];
                sell[i] = 0;
            }
            for (int i = 1; i < n; ++i)
            {
                for (int j = 1; j <= k; j++)
                {
                    buy[j] = Math.Max(buy[j], -prices[i]);
                    sell[j] = Math.Max(sell[j], buy[j] + prices[i]);
                    Console.WriteLine($"buy[{j}] = {buy[j]}, sell[{j}] = {sell[j]}");
                }
            }
            return sell[k];
        }

        public int[] SortByBits(int[] arr)
        {
            int[] res = new int[arr.Length];
            Dictionary<int, int> dict = new Dictionary<int, int>();

            foreach (var item in arr)
            {
                dict.Add(item, 0);
            }

            for (int i = 0; i < arr.Length; i++)
            {
                int temp = arr[i];
                while (temp > 0)
                {
                    dict[arr[i]] += temp % 2;
                    temp /= 2;
                }
            }
            return res;
        }




        public bool CanVisitAllRooms(IList<IList<int>> rooms)
        {
            int n = rooms.Count;
            int count = 0;
            bool[] visit = new bool[n];

            Queue<int> queue = new Queue<int>();
            visit[0] = true;
            queue.Enqueue(0);

            while (queue.Count > 0)
            {
                int index = queue.Dequeue();
                count++;

                foreach (var key in rooms[index])
                {
                    if (!visit[key])
                    {
                        visit[key] = true;
                        queue.Enqueue(key);
                    }
                }
            }
            return count == n;
        }




        // Console.WriteLine($"dp[{j}] = {dp[j]}");
    }
}